In two-tiered Wireless Sensor Networks (WSNs) relay node placement is one ofthe key factors impacting the network energy consumption and the systemoverhead. In this paper, a novel connectivity-aware approximation algorithm forrelay node placement in WSNs is proposed to offer a major step forward insaving system overhead. Specifically, a unique Local Search ApproximationAlgorithm (LSAA) is introduced to solve the Relay Node Single Cover (RNSC)problem. In this proposed LSAA approach, the sensor nodes are allocated intogroups and then a local Set Cover (SC) for each group is achieved by a localsearch algorithm. The union set of all local SCs constitutes a SC of the RNSCproblem. The approximation ratio and the time complexity of the LSAA areanalyzed by rigorous proof. Additionally, the LSAA approach has been extendedto solve the relay node double cover problem. Then, a Relay Location SelectionAlgorithm (RLSA) is proposed to utilize the resulting SC from LSAA in combiningRLSA with the minimum spanning tree heuristic to build the high-tierconnectivity. As the RLSA searches for a nearest location to the sink node foreach relay node, the high-tier network built by RLSA becomes denser than thatby existing works. As a result, the number of added relay nodes for buildingthe connectivity of the high-tier WSN can be significantly saved. Simulationresults clearly demonstrate that the proposed LSAA outperforms the approachesreported in literature and the RLSA-based algorithm can noticeably save relaynodes newly deployed for the high-tier connectivity.
展开▼
